{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Coin Change II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: change"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #零钱兑换 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>coins</code> 表示不同面额的硬币，另给一个整数 <code>amount</code> 表示总金额。</p>\n",
    "\n",
    "<p>请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>假设每一种面额的硬币有无限个。 </p>\n",
    "\n",
    "<p>题目数据保证结果符合 32 位带符号整数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>amount = 5, coins = [1, 2, 5]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>有四种方式可以凑成总金额：\n",
    "5=5\n",
    "5=2+2+1\n",
    "5=2+1+1+1\n",
    "5=1+1+1+1+1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>amount = 3, coins = [2]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>只用面额 2 的硬币不能凑成总金额 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>amount = 10, coins = [10] \n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= coins.length <= 300</code></li>\n",
    "\t<li><code>1 <= coins[i] <= 5000</code></li>\n",
    "\t<li><code>coins</code> 中的所有值 <strong>互不相同</strong></li>\n",
    "\t<li><code>0 <= amount <= 5000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [coin-change-ii](https://leetcode.cn/problems/coin-change-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [coin-change-ii](https://leetcode.cn/problems/coin-change-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[1,2,5]', '3\\n[2]', '10\\n[10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Change the first char != 'a' to 'a', unless the char is at the middle of an odd-length palindrome.\n",
    "    If the palindrome consists of only 'a's, change the last char to 'b'.\n",
    "    Time complexity: O(n). Space complexity: O(1) (neglecting the output string).\n",
    "    '''\n",
    "    def breakPalindrome(self, palindrome: str) -> str:\n",
    "        n = len(palindrome)\n",
    "        if n == 1:\n",
    "            return ''\n",
    "\n",
    "        res = ''\n",
    "        for i in range(n):\n",
    "            if palindrome[i] != 'a':\n",
    "                if not (n % 2 != 0 and i == n // 2):\n",
    "                    return res + 'a' + palindrome[i+1:]\n",
    "            if i == n - 1:\n",
    "                return res + 'b'\n",
    "            res += palindrome[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        \n",
    "        n = len(coins)\n",
    "        dp = [[0]*(amount+1) for _ in range(n+1)]   # 初始化\n",
    "        dp[0][0] = 1    # 合法的初始化\n",
    "        \n",
    "        # 完全背包：优化后的状态转移\n",
    "        for i in range(1, n+1):         # 第一层循环：遍历硬币\n",
    "            for j in range(amount+1):   # 第二层循环：遍历背包\n",
    "                if j < coins[i-1]:      # 容量有限，无法选择第i个硬币\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:                   # 可选择第i个硬币\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]\n",
    "        \n",
    "        return dp[n][amount]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount, coins):\n",
    "        \"\"\"\n",
    "        :type amount: int\n",
    "        :type coins: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        memo = [0] * (amount + 1)\n",
    "        memo[0] = 1\n",
    "\n",
    "        for change in coins:\n",
    "            for i in range(change, len(memo)):\n",
    "                memo[i] += memo[i - change]\n",
    "                \n",
    "        return memo[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount, coins):\n",
    "        \"\"\"\n",
    "        :type amount: int\n",
    "        :type coins: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = [1]+[0]*(amount)\n",
    "        print(dp)\n",
    "        for i in range(len(coins)):\n",
    "            for j in range(coins[i],amount+1):\n",
    "                dp[j] += dp[j-coins[i]]\n",
    "        return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        n = len(coins)\n",
    "        dp = [0 for _ in range(amount+1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(n):\n",
    "            for j in range(coins[i],amount+1):\n",
    "                dp[j] = dp[j] + dp[j-coins[i]]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp = [0]*(amount+1)\n",
    "        dp[0] = 1\n",
    "        for coin in coins:\n",
    "            for i in range(coin, amount+1):\n",
    "                dp[i] += dp[i-coin]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp = [0] * (amount + 1)\n",
    "        dp[0] = 1\n",
    "        \n",
    "        for coin in coins:\n",
    "            for i in range(coin, amount + 1):\n",
    "                dp[i] += dp[i-coin]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp = [0] * (amount+1)\n",
    "        dp[0] = 1\n",
    "\n",
    "        for c in coins:\n",
    "            for i in range(c,amount+1):\n",
    "                dp[i] += dp[i-c]\n",
    "        return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp = [0]*(amount+1)\n",
    "        dp[0] = 1\n",
    "    \n",
    "        for coin in coins:\n",
    "            for i in range(1, amount+1):\n",
    "                if coin <= i:\n",
    "                    dp[i] += dp[i-coin]\n",
    "        return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        \n",
    "        dp = [0] * (amount + 1)\n",
    "        dp[0] = 1\n",
    "        for coin in coins:\n",
    "            for j in range(amount+1):\n",
    "                if coin <=j :\n",
    "                    dp[j] = dp[j] + dp[j-coin]\n",
    "\n",
    "        return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp = [0] * (amount+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(len(coins)):\n",
    "            for j in range(coins[i],amount+1):\n",
    "                dp[j] += dp[j-coins[i]]\n",
    "        return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp = [0] * (amount + 1)\n",
    "\n",
    "        dp[0] = 1\n",
    "\n",
    "        for coin in coins:\n",
    "            for i in range(coin, amount+1):\n",
    "                dp[i] = dp[i] + dp[i-coin]\n",
    "        \n",
    "        return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp = [1] + [0]* amount\n",
    "\n",
    "        for x in coins:\n",
    "            for y in range(x, amount+1):\n",
    "                dp[y] = dp[y] + dp[y-x]\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        n=len(coins)\n",
    "        dp={0:1}\n",
    "        for i in range(n):\n",
    "            money=coins[i]\n",
    "            ori_dp=dp.copy()\n",
    "            key_list=list(ori_dp.keys())\n",
    "\n",
    "            for key in key_list:\n",
    "                j=1\n",
    "                ori=ori_dp[key]\n",
    "                while(j*money+key<=amount):\n",
    "                   # print(money,key,j*money+key)\n",
    "                    if not j*money+key in dp.keys():\n",
    "                        dp[j*money+key]=ori\n",
    "                    else:\n",
    "                        dp[j*money+key]+=ori\n",
    "                    j+=1\n",
    "        if not amount in dp.keys():\n",
    "            return 0\n",
    "      #  print(dp)\n",
    "        return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp=[0]*(amount+1)# d[i]: 总金额为i时的硬币组合数\n",
    "        dp[0]=1\n",
    "        for i in range(len(coins)):\n",
    "            for j in range(coins[i], amount+1):\n",
    "                dp[j]+=dp[j-coins[i]]\n",
    "            print(dp)\n",
    "        return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        if amount == 0:\n",
    "            return 1\n",
    "\n",
    "        ## dp[j] 可以凑成金额j的组合数\n",
    "\n",
    "        dp = [0] * (amount + 1)\n",
    "        for i in range(0, amount + 1):\n",
    "            if i % coins[0] == 0:\n",
    "                dp[i] = 1\n",
    "        for i in range(1, len(coins)):\n",
    "            for j in range(coins[i], amount + 1):\n",
    "                dp[j] += dp[j - coins[i]]\n",
    "            print(dp)\n",
    "        return dp[-1]\n",
    "        # print(dp)\n",
    "        # return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        # if amount == 0:\n",
    "        #     return 1\n",
    "\n",
    "        ## dp[j] 可以凑成金额j的组合数\n",
    "\n",
    "        dp = [0] * (amount + 1)\n",
    "        for i in range(0, amount + 1):\n",
    "            if i % coins[0] == 0:\n",
    "                dp[i] = 1\n",
    "        for i in range(1, len(coins)):\n",
    "            for j in range(coins[i], amount + 1):\n",
    "                dp[j] += dp[j - coins[i]]\n",
    "            print(dp)\n",
    "        return dp[-1]\n",
    "        # print(dp)\n",
    "        # return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def clean_change(self, amount: int, coins: List[int]) -> int:\n",
    "        # print(f'amount={amount}, coins={coins}')\n",
    "        if amount == 0:\n",
    "            return 1 \n",
    "        n = len(coins)\n",
    "        if n == 1:\n",
    "            if amount % coins[0] == 0:\n",
    "                return 1\n",
    "            return 0\n",
    "        max_coin = coins[-1]\n",
    "        if amount not in self.coin_comb:\n",
    "            self.coin_comb[amount] = {}\n",
    "        n_ways_wo_max = self.clean_change(amount, coins[:-1])  # no max coin\n",
    "\n",
    "        if max_coin in self.coin_comb[amount]:\n",
    "            # read from cache\n",
    "            n_ways_with_max = self.coin_comb[amount][max_coin]\n",
    "        else:\n",
    "            # write to cache\n",
    "            n_ways_with_max = 0\n",
    "            for n_max_coin in range(1, amount // max_coin + 1):\n",
    "                new_amount = amount - n_max_coin * max_coin\n",
    "                curr_ways = self.clean_change(new_amount, coins[:-1])\n",
    "                # if (max_coin, n_max_coin) not in self.coin_comb[amount]:\n",
    "                #     curr_ways = self.clean_change(new_amount, coins[:-1])\n",
    "                #     self.coin_comb[amount][max_coin, n_max_coin] = curr_ways\n",
    "                # else:\n",
    "                #     curr_ways = self.coin_comb[amount][max_coin, n_max_coin]\n",
    "                n_ways_with_max += curr_ways\n",
    "            self.coin_comb[amount][max_coin] = n_ways_with_max\n",
    "        \n",
    "        # return both with and without this max coin\n",
    "        return n_ways_with_max + n_ways_wo_max\n",
    "\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        if 0 < amount < min(coins): \n",
    "            return 0\n",
    "        elif amount == 0:\n",
    "            return 1\n",
    "        coins = sorted([coin for coin in coins if coin <= amount])\n",
    "        self.coin_comb = {}  # {amount: {max_coin: n_ways}}\n",
    "\n",
    "        out = self.clean_change(amount, coins)\n",
    "        print(self.coin_comb)\n",
    "        return out "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        # 典型完全背包问题\n",
    "        dp = [0] * (amount+1)\n",
    "        dp[0] = 1\n",
    "        def f(j,coin):\n",
    "            dp[j] += dp[j-coin]\n",
    "        [f(j,coin) for coin in coins if coin < amount+1 for j in range(coin, amount+1)]\n",
    "        return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp = [defaultdict(int) for _ in range(amount + 1)]\n",
    "        coins.sort()\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, amount + 1):\n",
    "            for coin in coins:\n",
    "                if i - coin >= 0:\n",
    "                    for k, v in dp[i - coin].items():\n",
    "                        if coin >= k:\n",
    "                            dp[i][coin] += v\n",
    "                else:\n",
    "                    break\n",
    "        return sum(dp[amount].values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        # dp[j]：凑成总⾦额j的货币组合数为dp[j]\n",
    "        # 要是先背包再物品则dp数组是：1、2、3、5、9\n",
    "        # 最后是9种结果，其实就是排列结果（5、11111、1112、1121、1211、2111、221、212、122），而本题要求的是组合结果\n",
    "        # 可以画一个动规图\n",
    "        dp = [0] * 750000\n",
    "        dp[0] = 1\n",
    "        for i in range(len(coins)):\n",
    "            for j in range(coins[i],amount+1):\n",
    "                dp[j] += dp[j-coins[i]]\n",
    "        return dp[amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        # dp[amount][max coin]\n",
    "        dp = defaultdict(lambda: defaultdict(int))\n",
    "        dp[0][0] = 1\n",
    "        for i in range(amount):\n",
    "            for min_coin in dp[i]:\n",
    "                for coin in coins:\n",
    "                    if coin >= min_coin and i+coin <= amount:\n",
    "                        dp[i+coin][coin] += dp[i][min_coin]\n",
    "            # print_dict(dp)\n",
    "        return sum(dp[amount].values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, amount, coins, checklist):\n",
    "        if amount == 0: return 1\n",
    "        if amount <coins[-1] or len(coins)==0:return 0\n",
    "        \n",
    "        N = len(coins)\n",
    "        if checklist[(amount, N)] != -1: return checklist[(amount, N)]\n",
    "        res = 0\n",
    "        for i in range(N):\n",
    "            res += self.dfs(amount-coins[i], coins[i:], checklist)\n",
    "        checklist[(amount, N)] = res\n",
    "        return res\n",
    "\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        if amount == 0: return 1\n",
    "        coins = sorted(coins, reverse = True)\n",
    "        checklist = collections.defaultdict(lambda:-1)\n",
    "        return self.dfs(amount, coins, checklist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        coins.sort(key=lambda x: -x)\n",
    "        d={}\n",
    "        return self.helper(amount,coins,0,d)\n",
    "\n",
    "    def helper(self,amount,coins,i,d):\n",
    "        if amount==0:\n",
    "            return 1\n",
    "        n=len(coins)\n",
    "        count=0\n",
    "        for j in range(i,n):\n",
    "            if coins[j]>amount:\n",
    "                continue\n",
    "            if (amount-coins[j],j) in d:\n",
    "                x=d[(amount-coins[j],j)]\n",
    "            else:\n",
    "                x=self.helper(amount-coins[j],coins,j,d)\n",
    "                d[(amount-coins[j],j)]=x\n",
    "            count+=x\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        # 状态，选择，dp[i][j]表示一共有多少种组合可以凑出, i 表示只使用前面的i种硬币凑出j数值的组合有多少种方法\n",
    "        memo = [[0] * (amount+1)] * (len(coins)+1)\n",
    "        n_coins = len(coins)\n",
    "\n",
    "        print(memo)\n",
    "        \n",
    "        # 定义我们的base case的情况\n",
    "        for i in range(1, len(coins)+1):\n",
    "            # 无论多少硬币都能凑出0元\n",
    "            memo[i][0] = 1\n",
    "\n",
    "        # for i in range(1, amount+1):\n",
    "        #     memo[0][i] = 0\n",
    "            \n",
    "        memo[0][0]=1\n",
    "        # 当遇到一个新的硬币，是否要把这个硬币加入到里面,注意，for的顺序不能用错。\n",
    "        for k in range(1, n_coins+1):\n",
    "            for j in range(1, amount+1):       \n",
    "                if j-coins[k-1] < 0:\n",
    "                    # 装都装不进去，忽略掉\n",
    "                    memo[k][j]=memo[k-1][j]\n",
    "                else:\n",
    "                    memo[k][j]=memo[k][j-coins[k-1]]+memo[k-1][j]\n",
    "        \n",
    "        return memo[len(coins)][amount]\n",
    "                    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp = [[0] * (amount + 1) for _ in range(len(coins))]\n",
    "        dp[0][0] = 1\n",
    "        dp = [0] * (amount+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(len(coins)):\n",
    "            for j in range(coins[i], amount + 1):\n",
    "                dp[j] += dp[j-coins[i]]\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp=[[0 for _ in range(amount+1)] for _ in range(len(coins))]\n",
    "        for j in range(amount+1):\n",
    "            if j%coins[0]!=0:\n",
    "                dp[0][j]=0\n",
    "            else:\n",
    "                dp[0][j]=1\n",
    "        #初始化\n",
    "        for i in range(1,len(coins)):\n",
    "            dp[i]=dp[i-1]\n",
    "            for j in range(coins[i],amount+1):\n",
    "                dp[i][j]=dp[i][j]+dp[i][j-coins[i]]\n",
    "        #状态转移方程\n",
    "        return dp[len(coins)-1][amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        dp = [[0] * (amount+1) for _ in range(len(coins))]\n",
    "        for j in range(amount+1):\n",
    "            if j%coins[0]!=0:\n",
    "                dp[0][j]=0\n",
    "            else:\n",
    "                dp[0][j]=1\n",
    "        for i in range(1, len(coins)):\n",
    "            dp[i] = dp[i-1]\n",
    "            for j in range(coins[i], amount+1):\n",
    "                dp[i][j] += dp[i][j-coins[i]]\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        # n = len(coins)\n",
    "        # #i下标 j当前和\n",
    "        # # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if j >= amount or i == n: return 1 if j == amount else 0\n",
    "        #     return dfs(i+1,j) + dfs(i, j+coins[i])\n",
    "        # return dfs(0,0)\n",
    "\n",
    "        '''\n",
    "            f[i,j] = f[i+1,j] + f[i,j+coins[i]]\n",
    "        '''\n",
    "\n",
    "        n = len(coins)\n",
    "        f = [[0]*(amount + 1) for _ in range(n+1)]\n",
    "        f[-1][amount] = 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(amount,-1,-1):\n",
    "                f[i][j] = f[i+1][j]\n",
    "                if j+coins[i] <= amount: f[i][j] += f[i][j+coins[i]]\n",
    "        return f[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        # n = len(coins)\n",
    "        # # 法1: 递归 -- 时间复杂度高\n",
    "        # def change_i(i, res):\n",
    "        #     if i == n:\n",
    "        #         if res == 0:\n",
    "        #             return 1\n",
    "        #         else:\n",
    "        #             return 0\n",
    "        #     zhang = 0\n",
    "        #     total = 0\n",
    "        #     while coins[i] * zhang <= res:\n",
    "        #         total += change_i(i+1, res-zhang*coins[i])\n",
    "        #         zhang += 1\n",
    "        #     return total\n",
    "        # return change_i(0, amount)\n",
    "\n",
    "        # 法2: dp\n",
    "        n = len(coins)\n",
    "        dp =[[0]* (amount+1) for _ in range(n+1)]\n",
    "        dp[n][0] = 1\n",
    "        i = n-1\n",
    "        while i >= 0:\n",
    "            for res in range(amount+1):\n",
    "                if res-coins[i]>= 0:\n",
    "                    dp[i][res] = dp[i][res-coins[i]] + dp[i+1][res]\n",
    "                else:\n",
    "                    dp[i][res] = dp[i+1][res]\n",
    "            i -= 1\n",
    "\n",
    "        return dp[0][amount]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        if amount==0: return 1\n",
    "        le=len(coins)\n",
    "        dp=[[0]*le for _ in range(amount+1) ]\n",
    "        dp[0]=[1]*le\n",
    "        x=[]\n",
    "        \n",
    "        for i in range(1,amount+1):\n",
    "            for j in range(le):\n",
    "                if i-coins[j]>0:\n",
    "                    for k in range(j+1):\n",
    "                        \n",
    "                        dp[i][j]+=dp[i-coins[j]][k]\n",
    "                elif i-coins[j]==0:\n",
    "                     dp[i][j]+=1\n",
    "\n",
    "\n",
    "            #print(i,dp[i])\n",
    "        return sum(dp[amount])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.D = {}\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        self.coins = coins\n",
    "        return self.f(len(coins),amount)\n",
    "    def f(self,i,j):\n",
    "        res = self.D.get((i,j))\n",
    "        if res is None:\n",
    "            if i == 1:\n",
    "                self.D[(i,j)] = 1 if j % self.coins[i-1] == 0 else 0\n",
    "            else:\n",
    "                self.D[(i,j)] = sum(self.f(i-1, j-k) for k in range(0,j+1,self.coins[i-1]))\n",
    "            res = self.D[(i,j)]\n",
    "        return res           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        coins.reverse()\n",
    "        return self.change_number(amount,coins,0,{})\n",
    "\n",
    "    def change_number(self,amount,coins,i,current_result):\n",
    "        if (amount,i) in current_result:\n",
    "            return current_result[amount,i]\n",
    "        if amount<0:\n",
    "            return 0\n",
    "        elif amount==0:\n",
    "            return 1\n",
    "        else:\n",
    "            if i==len(coins)-1:\n",
    "                current_result[amount,i]=1 if amount%coins[i]==0 else 0\n",
    "                return current_result[amount,i]\n",
    "            else:\n",
    "                current_result[amount,i]=self.change_number(amount-coins[i],coins,i,current_result)+self.change_number(amount,coins,i+1,current_result)\n",
    "                return current_result[amount,i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        self.d = {}\n",
    "        return self.dp(coins, len(coins)-1, amount)\n",
    "\n",
    "    def dp(self, coins, idx, amount):\n",
    "        if amount == 0:\n",
    "            return 1\n",
    "        if idx ==-1 and amount != 0:\n",
    "            return 0\n",
    "        if str(idx) + \"_\" + str(amount) in self.d:\n",
    "            return self.d[str(idx) + \"_\" + str(amount)]\n",
    "        if coins[idx] <= amount:\n",
    "            res = self.dp(coins, idx, amount-coins[idx]) + self.dp(coins, idx-1, amount)\n",
    "            self.d[str(idx) + \"_\" + str(amount)] = res\n",
    "            return res\n",
    "        else:\n",
    "            res = self.dp(coins, idx-1, amount)\n",
    "            self.d[str(idx) + \"_\" + str(amount)] = res\n",
    "            return res\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def change(self, amount: int, coins: List[int]) -> int:\n",
    "#         if amount == 0: return 0\n",
    "#         memo = [-1] * (amount + 1)\n",
    "#         memo[0] = 1\n",
    "        \n",
    "#         def dp(amount): \n",
    "#             '''\n",
    "#             return the number of ways to make up amount\n",
    "#             '''\n",
    "#             if amount < 0: \n",
    "#                 return 0\n",
    "#             if memo[amount] != -1: \n",
    "#                 return memo[amount]\n",
    "#             ways = 0\n",
    "#             for coin in coins: \n",
    "#                 ways += dp(amount - coin)\n",
    "#             memo[amount] = ways\n",
    "#             return ways\n",
    "        \n",
    "#         return dp(amount)\n",
    "\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        # Initialize a memoization dictionary to denote uncalculated states\n",
    "        memo = {}\n",
    "        # Base case is handled within the recursive function\n",
    "        \n",
    "        return self.dp(amount, coins, len(coins) - 1, memo)\n",
    "\n",
    "    def dp(self, amount: int, coins: List[int], last_index: int, memo: dict) -> int:\n",
    "        # If this state is already calculated, return it\n",
    "        if (amount, last_index) in memo:\n",
    "            return memo[(amount, last_index)]\n",
    "        \n",
    "        # If amount is zero, there's one way to make it (using zero coins)\n",
    "        if amount == 0:\n",
    "            return 1\n",
    "        \n",
    "        # If amount is negative or no more coins are left, there are 0 ways\n",
    "        if amount < 0 or last_index < 0:\n",
    "            return 0\n",
    "        \n",
    "        # Initialize number of ways to make `amount` using coins\n",
    "        num_ways = 0\n",
    "        \n",
    "        # Include the coin at last_index\n",
    "        num_ways += self.dp(amount - coins[last_index], coins, last_index, memo)\n",
    "        \n",
    "        # Exclude the coin at last_index\n",
    "        num_ways += self.dp(amount, coins, last_index - 1, memo)\n",
    "        \n",
    "        # Store the result into memo and return it\n",
    "        memo[(amount, last_index)] = num_ways\n",
    "        \n",
    "        return num_ways\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        if amount == 0: return 1\n",
    "        dp = collections.defaultdict(dict)\n",
    "        def dfs(i, prev):\n",
    "            cache = dp[i].get(prev, -1)\n",
    "            if cache != -1:\n",
    "                return cache\n",
    "            ans = 0\n",
    "            for c in coins:\n",
    "                if c > prev:\n",
    "                    continue\n",
    "                left = i - c\n",
    "                if left == 0:\n",
    "                    ans +=1\n",
    "                elif left > 0:\n",
    "                    ans += dfs(left, c)\n",
    "            dp[i][prev] = ans\n",
    "            return ans\n",
    "        return dfs(amount, inf)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # dp 思路：dp(i,j) 表示只使用前 i 个面值，凑出总金额 j 的方式\n",
    "    # dp(i, j) = dp(i-1,j) + dp(i, j-coins[i-1])\n",
    "    # i == 0 时，返回 0，j == 0 时，返回 1\n",
    "    def dp(self, i, j, coins):\n",
    "        if i == 0:\n",
    "            return 0\n",
    "        if j == 0:\n",
    "            return 1\n",
    "        if self.memo[i][j] != -1:\n",
    "            return self.memo[i][j]\n",
    "        if j - coins[i-1] >= 0:\n",
    "            self.memo[i][j] = self.dp(i-1, j, coins) + self.dp(i, j-coins[i-1], coins)\n",
    "        else:\n",
    "            self.memo[i][j] = self.dp(i-1, j, coins)\n",
    "        return self.memo[i][j]\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        self.memo = [[-1] * (amount+1) for _ in range(len(coins)+1)]\n",
    "        return self.dp(len(coins), amount, coins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = []\n",
    "\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        n = len(coins)\n",
    "        self.memo = [[-1] * (amount + 1) for _ in range(n)]\n",
    "        return self.dp(amount, coins, 0)\n",
    "\n",
    "    def dp(self, amount, coins, i):\n",
    "        if amount == 0:\n",
    "            return 1\n",
    "        if i >= len(coins):\n",
    "            return 0\n",
    "        if self.memo[i][amount] != -1:\n",
    "            return self.memo[i][amount]\n",
    "        \n",
    "        if coins[i] > amount:\n",
    "            self.memo[i][amount] = self.dp(amount, coins, i + 1)\n",
    "        else:\n",
    "            self.memo[i][amount] = self.dp(amount, coins, i + 1) + self.dp(amount - coins[i], coins, i)\n",
    "\n",
    "        return self.memo[i][amount]\n",
    "\n",
    "    # def __init__(self):\n",
    "    #     self.memo = []\n",
    "\n",
    "    # def change(self, amount: int, coins: List[int]) -> int:\n",
    "    #     self.memo = [[-1] * (amount + 1) for _ in range(len(coins))]\n",
    "    #     return self.dp(amount, coins, 0)\n",
    "    \n",
    "    # def dp(self, amount, coins, i):\n",
    "    #     if amount == 0:\n",
    "    #         return 1\n",
    "\n",
    "    #     if i >= len(coins):\n",
    "    #         return 0\n",
    "        \n",
    "    #     if self.memo[i][amount] != -1:\n",
    "    #         return self.memo[i][amount]\n",
    "        \n",
    "    #     if coins[i] > amount:\n",
    "    #         self.memo[i][amount] = self.dp(amount, coins, i + 1)\n",
    "    #     else:\n",
    "    #         self.memo[i][amount] = self.dp(amount - coins[i], coins, i) + self.dp(amount, coins, i + 1)\n",
    "        \n",
    "    #     return self.memo[i][amount]\n",
    "\n",
    "    # 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "    # 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。\n",
    "    # def change(self, amount: int, coins: List[int]) -> int:\n",
    "    #     dp = [[0] * (amount + 1) for _ in range(len(coins))]\n",
    "    #     for i in range(len(coins)):\n",
    "    #         dp[i][0] = 1\n",
    "\n",
    "    #     for i in range(len(coins)):\n",
    "    #         for j in range(1, amount + 1):\n",
    "    #             if coins[i] > j:\n",
    "    #                 dp[i][j] = dp[i - 1][j]\n",
    "    #             else:\n",
    "    #                 dp[i][j] = dp[i][j - coins[i]] + dp[i - 1][j]\n",
    "\n",
    "    #     return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        \n",
    "        n = len(coins)\n",
    "        dp = [[0]*(amount+1) for _ in range(n+1)]   # 初始化\n",
    "        dp[0][0] = 1    # 合法的初始化\n",
    "        \n",
    "        # 完全背包：优化后的状态转移\n",
    "        for i in range(1, n+1):         # 第一层循环：遍历硬币\n",
    "            for j in range(amount+1):   # 第二层循环：遍历背包\n",
    "                if j < coins[i-1]:      # 容量有限，无法选择第i个硬币\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:                   # 可选择第i个硬币\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]\n",
    "        \n",
    "        return dp[n][amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def change(self, amount, coins):\n",
    "        n = len(coins)\n",
    "        dp = [[0] * (amount + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0] = 1\n",
    "            for j in range(1, amount + 1):\n",
    "                if j >= coins[i - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        n = len(coins)\n",
    "        dp = [[0 for j in range(amount + 1)] for i in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, amount + 1):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                if j >= coins[i - 1]:\n",
    "                    dp[i][j] += dp[i][j - coins[i - 1]]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # def change(self, amount: int, coins: List[int]) -> int:\n",
    "    #     from functools import lru_cache\n",
    "\n",
    "    #     # @lru_cache\n",
    "    #     def dp(n: int, steps: []) -> int:\n",
    "    #         if n == 0:\n",
    "    #             key = \",\".join(map(lambda x: str(x), sorted(steps)))\n",
    "    #             if key not in ans:\n",
    "    #                 ans.add(key)\n",
    "    #                 return 1\n",
    "\n",
    "    #             return 0\n",
    "\n",
    "    #         # if n in memo:\n",
    "    #         #     return memo[n]\n",
    "\n",
    "    #         ways = 0\n",
    "    #         for coin in coins:\n",
    "    #             if n - coin >= 0:\n",
    "    #                 ways += dp(n - coin, steps + [coin])\n",
    "    #         memo[n] = ways\n",
    "    #         return ways\n",
    "\n",
    "    #     ans = set()\n",
    "\n",
    "    #     memo = {}\n",
    "    #     return dp(amount, [])\n",
    "\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        i=amount\n",
    "        j=count of coins\n",
    "        dp[i][j]=dp[i][j-1] + dp[i-coins[j]][j]\n",
    "        \"\"\"\n",
    "\n",
    "        m = len(coins)\n",
    "\n",
    "        dp = [[0 for _ in range(m + 1)] for _ in range(amount + 1)]\n",
    "\n",
    "        for j in range(m + 1):\n",
    "            dp[0][j] = 1\n",
    "\n",
    "        for i in range(1, amount + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                if i >= coins[j - 1]:\n",
    "                    dp[i][j] = dp[i][j - 1] + dp[i - coins[j - 1]][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        n = len(coins)\n",
    "        f = [([0] * (amount+1)) for i in range(n+1)]\n",
    "        print(f)\n",
    "        f[0][0] = 1\n",
    "        print(f)\n",
    "        for i in range(1,n+1):\n",
    "            val = coins[i-1]\n",
    "            #print(f)\n",
    "            for j in range(amount+1):\n",
    "                #print(i,j)\n",
    "                #print(f[i][j])\n",
    "                f[i][j] = f[i-1][j]\n",
    "                k = 1\n",
    "                while k*val <= j:\n",
    "                    f[i][j] = f[i][j] + f[i-1][j-k*val]\n",
    "                    k = k+1\n",
    "        #print(f)\n",
    "        return f[n][amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        # dp[i][j]表示从前i个硬币中任选，得到j金额的方案数\n",
    "        dp = [[0] * (amount + 1) for i in range(len(coins))]\n",
    "        \n",
    "        dp[0][0] = 1 \n",
    "        for j in range(1, amount + 1): # 第0个硬币能得到金额j的方案数\n",
    "            if j >= coins[0]:\n",
    "                dp[0][j] = dp[0][j - coins[0]]\n",
    "\n",
    "        for i in range(len(coins)): #对于所有金额为0的方案数\n",
    "            dp[i][0] = 1\n",
    "        print(dp[0])\n",
    "        for i in range(1, len(coins)):\n",
    "            for j in range(1, amount + 1):\n",
    "                # 不选当前这个硬币, 就能凑成金额j\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                if j == coins[i]: #选这个硬币\n",
    "                    dp[i][j] += 1\n",
    "                elif j > coins[i]:\n",
    "                    # 选当前这个硬币, 可以凑成金额j-> 又可以拆分成“之前从没选过现在选”，或“之前就选过，这次继续选”\n",
    "                    dp[i][j] += dp[i][j - coins[i]] \n",
    "            print(dp[i])\n",
    "        return dp[-1][-1]\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        @cache\n",
    "        def df(i, j):\n",
    "            if j == 0:\n",
    "                return 1\n",
    "            \n",
    "            if i == 0:\n",
    "                return int(j % coins[0] == 0)\n",
    "            \n",
    "            res = 0\n",
    "            for k in range(0, j + 1, coins[i]):\n",
    "                res += df(i - 1, j - k)\n",
    "            return res\n",
    "        return df(len(coins) - 1, amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        if amount==0:\n",
    "            return 1\n",
    "        coins.sort()\n",
    "        lenOfCoins=len(coins)\n",
    "        if amount<coins[0]:\n",
    "            return 0\n",
    "        ll=[[-1]*(amount+1) for i in range(lenOfCoins)]\n",
    "\n",
    "        for i in range(lenOfCoins):\n",
    "            ll[i][0]=1\n",
    "\n",
    "        def cul(m,l):\n",
    "            if(m==0):\n",
    "                return 1\n",
    "            if l==lenOfCoins:\n",
    "                return 0\n",
    "            if(ll[l][m]!=-1):\n",
    "                return ll[l][m]\n",
    "            ll[l][m]=0\n",
    "            ll[l][m]+=cul(m,l+1)\n",
    "            i=coins[l]\n",
    "            mm=m\n",
    "            while (mm>=i):\n",
    "                ll[l][m]+=cul(mm-i,l+1)\n",
    "                mm-=i     \n",
    "            return ll[l][m]\n",
    "        cul(amount,0)\n",
    "        return ll[0][amount]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        r = [{-math.inf:1}]\n",
    "        for i in range(1, amount+1):\n",
    "            ri = defaultdict(int)\n",
    "            for ci in coins:\n",
    "                if i >= ci:\n",
    "                    ri[ci] = sum([v for k,v in r[i-ci].items() if k <= ci])\n",
    "            r.append(ri)\n",
    "        return sum(r[-1].values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #2D DP\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        n = len(coins)\n",
    "        dp = [[0]* (amount+1) for _ in range(n)]\n",
    "        j = 0\n",
    "        while j * coins[0] <= amount:\n",
    "            dp[0][j * coins[0]] = 1\n",
    "            j += 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(amount+1):\n",
    "                res = 0\n",
    "                k = 0\n",
    "                while k * coins[i] <= j:\n",
    "                    res += dp[i-1][j-k*coins[i]]\n",
    "                    k += 1\n",
    "                dp[i][j] = res\n",
    "        return dp[n-1][amount]\n",
    "\n",
    "    #2D DP, improved space\n",
    "    # def change(self, amount: int, coins: List[int]) -> int:\n",
    "    #     n = len(coins)\n",
    "    #     dp = [1] + [0]* amount\n",
    "    #     for i in range(1, n+1):\n",
    "    #         for j in reversed(range(amount+1)):\n",
    "    #             res = 0\n",
    "    #             k = 0\n",
    "    #             while k * coins[i-1] <= j:\n",
    "    #                 res += dp[j-k*coins[i-1]]\n",
    "    #                 k += 1\n",
    "    #             dp[j] = res\n",
    "    #     return dp[amount]\n",
    "\n",
    "    #1D DP\n",
    "    # def change(self, amount: int, coins: List[int]) -> int:\n",
    "    #     n = len(coins)\n",
    "    #     dp = [[0] * (amount+1) for _ in range(n)]\n",
    "    #     j = 0\n",
    "    #     while j * coins[0] <= amount:\n",
    "    #         dp[0][j * coins[0]] = 1\n",
    "    #         j += 1\n",
    "    #     for i in range(1, n):\n",
    "    #         for j in range(amount+1):\n",
    "    #             dp[i][j] = dp[i-1][j]\n",
    "    #             if j >= coins[i]:\n",
    "    #                 dp[i][j] += dp[i][j-coins[i]]\n",
    "    #     return dp[n-1][amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        n = len(coins)\n",
    "        dp = [[0] * (amount + 1) for _ in range(n+1)]\n",
    "        \n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i, x in enumerate(coins):\n",
    "            for j in range(amount+1):\n",
    "                for k in range(j // x + 1):\n",
    "                    dp[i+1][j] += dp[i][j - k * x]\n",
    "\n",
    "        return dp[n][amount]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        #完全背包，每个物品取无限次\n",
    "        #计数，dp[i][j]，1<=i<=n, 0<=j<=amount，代表前i个物品，放入不超过j的背包的计数\n",
    "        #dp[i][j] = dp[i-1][j]+dp[i-1][j-weight[i]*k] k>=1\n",
    "        n = len(coins)\n",
    "        dp = [[0]*(amount+1) for i in range(0,n+1)]\n",
    "        dp[0][0] = 1 #倒凑出来的\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(0,amount+1):\n",
    "                k=0\n",
    "                while(k * coins[i-1] <= j):\n",
    "                    dp[i][j] += dp[i-1][j-k*coins[i-1]]\n",
    "                    k=k+1\n",
    "        # for i in range(0,n+1):\n",
    "        #     for j in range(0,amount+1):\n",
    "        #         print(i,j,dp[i][j])\n",
    "        #     print('\\n')\n",
    "        return dp[n][amount]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        memo = {}\n",
    "        coins = sorted(coins)\n",
    "        return self.dfs(amount, coins, 0, 0, memo)\n",
    "\n",
    "    def dfs(self, amount, coins, index, current_sum, memo):\n",
    "        if (current_sum, index) in memo:\n",
    "            return memo[(current_sum, index)]\n",
    "\n",
    "        if index == len(coins):\n",
    "            return 0\n",
    "                \n",
    "\n",
    "        if current_sum == amount:\n",
    "            return 1\n",
    "\n",
    "        if current_sum + coins[index] > amount:\n",
    "            return 0\n",
    "\n",
    "\n",
    "        take = self.dfs(amount, coins, index, current_sum + coins[index], memo)\n",
    "        skip = self.dfs(amount, coins, index + 1, current_sum, memo)\n",
    "\n",
    "        memo[(current_sum, index)] = take + skip\n",
    "\n",
    "        return memo[(current_sum, index)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.coins = None\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        self.coins = coins\n",
    "        return self.recursion(amount, len(coins) - 1)\n",
    "    \n",
    "    @cache\n",
    "    def recursion(self, num, border):\n",
    "        if border == 0:\n",
    "            return 1 if num % self.coins[border] == 0 else 0\n",
    "        ret = 0\n",
    "        for i in range(0, num + 1, self.coins[border]):\n",
    "            ret += self.recursion(num - i, border - 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j == 0: return 1\n",
    "            if i < 0: return 0\n",
    "\n",
    "            res = 0\n",
    "            for k in range(j // coins[i] + 1):\n",
    "                res += dfs(i-1, j - k * coins[i])\n",
    "            return res\n",
    "        n = len(coins)\n",
    "        return dfs(n-1, amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        n = len(coins)\n",
    "        v = amount\n",
    "        # dp = [[0] * (v + 1) for _ in range(n+1)]\n",
    "        # dp[0][0] = 1\n",
    "        # for i in range(n+1):\n",
    "        #     dp[i][0] = 1\n",
    "        # for i in range(1, n + 1):\n",
    "        #     for j in range(1, v + 1):\n",
    "        #         if j-coins[i-1] >= 0:\n",
    "        #             dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]\n",
    "        #         else:\n",
    "        #             dp[i][j] = dp[i-1][j]\n",
    "        # return dp[n][v]\n",
    "        store = {}\n",
    "        def max_comb(i, v):\n",
    "            nonlocal store\n",
    "            if i == 0 and v == 0:\n",
    "                return 1\n",
    "            elif i == 0:\n",
    "                return 0\n",
    "            elif v == 0:\n",
    "                return 1\n",
    "            \n",
    "            if (i,v) in store:\n",
    "                return store[(i, v)]\n",
    "            else:\n",
    "                if v - coins[i-1] >= 0:\n",
    "                    store[(i, v)] = max_comb(i-1, v) + max_comb(i, v - coins[i-1])\n",
    "                else:\n",
    "                    store[(i, v)] = max_comb(i-1, v)\n",
    "                return store[(i, v)]\n",
    "        return max_comb(n, v)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, cnt: int):\n",
    "            if cnt == 0: return 1\n",
    "            if i < 0 or cnt < 0: return 0\n",
    "            ans = 0\n",
    "            for j in range(math.ceil(cnt // coins[i]) + 1):\n",
    "                ans += dfs(i - 1, cnt - j * coins[i])\n",
    "            return ans\n",
    "        return dfs(len(coins) - 1, amount)\n",
    "        # n = len(coins)\n",
    "        # dp = [[0] * (amount + 1) for i in range(n + 1)]\n",
    "        # for i in range(n + 1):\n",
    "        #     dp[i][0] = 1\n",
    "        # for i in range(n - 1, -1, -1):\n",
    "        #     for j in range(amount + 1):\n",
    "        #         for k in range(math.ceil(j // coins[i]) + 1):\n",
    "        #             if j >= k * coins[i]:\n",
    "        #                 dp[i][j] += dp[i + 1][j - k * coins[i]]\n",
    "        # return dp[0][amount]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def change(self, amount: int, coins: List[int]) -> int:\n",
    "    n = len(coins)\n",
    "    coins.sort()\n",
    "    cache = {i: {} for i in range(n)}\n",
    "\n",
    "    def dfs(i, cur):\n",
    "      if cur >= amount: return 1 if cur == amount else 0\n",
    "      if cur not in cache[i].keys():\n",
    "        ans = 0\n",
    "        for j in range(i, n): ans += dfs(j, cur + coins[j]) \n",
    "        cache[i][cur] = ans\n",
    "      return cache[i][cur]\n",
    "    \n",
    "    return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        n=len(coins)\n",
    "        dp=[[-1 for _ in range(amount+1)] for _ in range(n+1)]\n",
    "        def dfs(idx,count):\n",
    "            if count==amount:\n",
    "                return 1\n",
    "            if count>amount or idx>=n:\n",
    "                return 0\n",
    "            if dp[idx][count]!=-1:\n",
    "                return dp[idx][count]\n",
    "            dp[idx][count]=dfs(idx+1,count)+dfs(idx,count+coins[idx])\n",
    "            return dp[idx][count]\n",
    "        return dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def change(self, amount: int, coins) -> int:\n",
    "        coins = sorted(coins, key=lambda x: -x)\n",
    "\n",
    "        @cache\n",
    "        def dfs(t, i):\n",
    "            if i >= len(coins):\n",
    "                if t == 0: return 1\n",
    "                return 0\n",
    "            if t == 0: return 1\n",
    "\n",
    "            if coins[i] > t: return dfs(t, i + 1)\n",
    "            return dfs(t - coins[i], i) + dfs(t, i + 1)\n",
    "        return dfs(amount, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        n = len(coins)\n",
    "        @cache\n",
    "        def dfs(i, amt):\n",
    "            if amt == 0:\n",
    "                return 1\n",
    "            if amt < 0 or i < 0:\n",
    "                return 0\n",
    "            # 选 / 不选\n",
    "            if coins[i] <= amt:\n",
    "                return dfs(i, amt - coins[i]) + dfs(i - 1, amt)\n",
    "\n",
    "            return dfs(i - 1, amt)\n",
    "\n",
    "        return dfs(n - 1, amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "from typing import List\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\r\n",
    "        n = len(coins)\r\n",
    "        @cache\r\n",
    "        def dfs(i,c):\r\n",
    "            \"\"\"\r\n",
    "            表示：选前i个硬币最小的硬币个数\r\n",
    "            \"\"\"\r\n",
    "            if i<0:\r\n",
    "                return 1 if c==0 else 0\r\n",
    "            ans =0\r\n",
    "            if c>=coins[i]:\r\n",
    "                ans = dfs(i,c-coins[i])+dfs(i-1,c)\r\n",
    "            else:\r\n",
    "                ans = dfs(i-1,c)\r\n",
    "            return ans\r\n",
    "        ans = dfs(n-1,amount)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins: List[int]) -> int:\n",
    "        n=len(coins)\n",
    "        @cache\n",
    "        def dfs(i,c):\n",
    "            if c==0:\n",
    "                return 1\n",
    "            if i<0:\n",
    "                return 0\n",
    "            if coins[i]>c:\n",
    "                return dfs(i-1,c)\n",
    "            return dfs(i,c-coins[i])+dfs(i-1,c)\n",
    "        return dfs(n-1,amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def change(self, amount: int, coins) :\n",
    "        weight=coins\n",
    "        value=coins\n",
    "        bagsize=amount\n",
    "        dp=[[0 for _ in range(bagsize+1)] for _ in range(len(weight)+1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(1, len(weight)+1):\n",
    "            for j in range(bagsize + 1):\n",
    "                if j < weight[i-1]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                else:\n",
    "                    dp[i][j] =dp[i - 1][j]+dp[i][j-weight[i-1]]\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
